class Solution:
    def getsum(self, x):
        ans = 0
        while x > 0:
            ans += x % 10
            x = x // 10
        return ans

    def dfs(self, i, j, m, n):
        if (i, j) in self.s or i >= m or j >= n or self.getsum(i)+self.getsum(j)>self.k:
            return
        self.s.add((i, j))
        self.dfs(i + 1, j, m, n)
        self.dfs(i, j + 1, m, n)

    def movingCount(self, m: int, n: int, k: int) -> int:
        self.k=k
        self.s = set()

        self.dfs(0, 0,m,n)
        print(self.s)
        return len(self.s)

if __name__ == '__main__':
    s = Solution()
    ans = s.movingCount(16,
                        8,
                        4)
    print(ans)
